package bit

import (
	"bytes"
	"fmt"
	"log"
	"math"
)

func absoluteValue(num int) uint {

	// 得到高位补码，负数-1，正数0
	// -1 = 1[0-30]0
	// 正数= num^iMask
	// 负数= (num+iMask)^iMask
	iMask := num >> 31
	res := (num + iMask) ^ iMask
	return uint(res)
}

type Bitmap struct {
	words    []uint64
	used     int
	capacity int // 2的指数
}

func New(cap int) *Bitmap {
	c := 0
	if (cap-1)&cap == 0 {
		c = cap
	} else {
		c = 1 << (int(math.Log2(float64(cap))) + 1)
	}
	return &Bitmap{capacity: c}
}
func (b *Bitmap) Has(num int) bool {
	i, offset := num/b.capacity, uint(num&(b.capacity-1))
	return i < len(b.words) && (b.words[i]&(1<<offset)) != 0
}

func (b *Bitmap) Add(num int) {
	if num > b.capacity {
		log.Panicf("oversize cap: %d, val:%d \r\n", b.capacity, num)
	}
	i, offset := num/b.capacity, uint(num&(b.capacity-1))
	for i >= len(b.words) {
		b.words = append(b.words, 0)
	}
	// 判断num是否已经存在bitmap中
	if b.words[i]&(1<<offset) == 0 {
		b.words[i] |= 1 << offset
		b.used++
	}
}

func (b *Bitmap) Len() int {
	return b.used
}

func (b *Bitmap) String() string {
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i, v := range b.words {
		if v == 0 {
			continue
		}
		for j := uint(0); j < 64; j++ {
			if v&(1<<j) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte(' ')
				}
				fmt.Fprintf(&buf, "%d", 64*uint(i)+j)
			}
		}
	}
	buf.WriteByte('}')
	fmt.Fprintf(&buf, "\t cap: %d, used: %d", b.capacity, b.used)
	return buf.String()
}

func XoR(param int) int {
	return param ^ param ^ param // 0^ param =param
}

func checkSum(pramas []int) int {
	p := 0
	for _, v := range pramas {
		p ^= v
	}
	return p
}

func miss(pramas []int, p int) int {
	for _, v := range pramas {
		p ^= v
	}
	return p
}
